package solution._0110._0113;

import common.TreeNode;

import java.util.*;

/**
 * Created by chen_snow
 * Date: 2021/7/6 22:35
 * Description: 路径总和 II
 */
public class Solution {

    public static void main(String[] args) {
        TreeNode node5 = new TreeNode(5);
        TreeNode node4 = new TreeNode(4);
        TreeNode node8 = new TreeNode(8);

        node5.left = node4;
        node5.right = node8;

        TreeNode node11 = new TreeNode(11);
        node4.left = node11;

        TreeNode node7 = new TreeNode(7);
        TreeNode node2 = new TreeNode(2);

        node11.left = node7;
        node11.right = node2;

        TreeNode node13 = new TreeNode(13);
        TreeNode node4_ = new TreeNode(4);
        node8.right = node4_;
        node8.left = node13;

        TreeNode node5_ = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        node4_.left = node5_;
        node4_.right = node1;

        pathSum(node5, 22);
    }

    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        backTrace(root, result, new ArrayDeque<>(), targetSum);
        return result;
    }

    public static void backTrace(TreeNode root, List<List<Integer>> result, Deque<Integer> data, int targetSum) {
        if (root == null) {
            return;
        }

        if (root.val == targetSum && root.left == null && root.right == null) {
            data.add(targetSum);
            result.add(new ArrayList<>(data));
            data.removeLast();
            return;
        }

        ArrayList<TreeNode> nodes = new ArrayList<>();
        if (root.left != null) {
            nodes.add(root.left);
        }
        if (root.right != null) {
            nodes.add(root.right);
        }

        for (TreeNode node : nodes) {
            data.offer(root.val);
            backTrace(node, result, data, targetSum - root.val);
            data.removeLast();
        }
    }
}
